package sword_offer;

import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName _54_kthLargestInTreeNode
 * @Description: 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 *  
 *
 * 限制：
 *
 * 1 ≤ k ≤ 二叉搜索树元素个数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:37
 */
public class _54_kthLargestInTreeNode {

    // 即位二叉搜索树，所以使用中序遍历统计位次即可
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    private int k = -1, res;

    public void dfs(TreeNode node){
        if (node == null)
            return;

        dfs(node.right);
        // 提前返回，如果当前k的结果已经是0，则直接返回
        if (k == 0)
            return;

        if (--k == 0)// k为1时 说明此时为目标元素，则设置res的值
            res = node.val;

        dfs(node.left);

    }

    // 迭代的方式 遍历树，统计节点得到最终答案
    public int kthLargestLoop(TreeNode root ,int k){
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            while (node != null){
                stack.addFirst(node);
                node = node.right;
            }
            node = stack.removeFirst();
            if (--k == 0)
                return node.val;
            node = node.left;
        }

        return 0;
    }






}
